Prime Circles (IP)

Is it always possible to arrange the numbers from 1 to 2n in a circle so that each adjacent pair sums to a prime? As of 2016, solutions have been found for every case up to n = 106 — but no one has yet proven that it’s always possible. From Futility Closet.

A circle of prime sums

I was intrigued by this mostly as a programming learning opportunity. A data structure for the circle of numbers could be a linked list. I have never implemented one of these in JavaScript and thought it would be a fun challenge. Additionally, the logical flow of the search for prime sums posed a second challenge. As you find prime sums you may get to a point where you can no longer find one and need to drop back and replace an earlier prime sum. So backtracking and keeping tabs on prime sums that have been eliminated poses the second challenge.

I am going to try something a little different here and write pseudocode to map out how I expect the program logic to flow.

  1. Given n generate an array containing the numbers 1 to 2n.
  2. Begin to generate our linked list by assigning 1 to the head node.
  3. Remove 1 from the array
  4. Try each of the numbers in the array until one is found that when added to 1 returns a prime.
  5. Remove that number from the array and generate a new node for this number.
  6. Repeat the search for the next number to provide a prime sum
  7. If one is not found then drop back a node
  8. Save the number that gave this prime pair separately from the array to keep it from being found again.
  9. Find a new prime pair and create the new node.
  10. Add the saved number back to the array.
  11. Continue finding prime pairs until the array is empty.
  12. Check to be sure the last node and the first node sum to a prime.
  13. If not drop back a node
  14. If the linked list is filled correctly, then make a picture of the number circle.

The linked list code used here is from Learners Bucket.

The limit is based solely on your patience. A limit of 100,000,000 takes about 20 seconds to calculate. Of course, the largest possible factorion is less than 99,999,999 as 8 X 9! = 2,903,040. Further digits do not grow fast enough as 9! < 1,000,000.



Enter a number <= 47 (n of 2n) for your circle and hit the button:


Reload the browser window/tab between calculations if you don't want successive calculations appended.